package com.zx._12_算法.algorithm.math;

import java.util.Arrays;
import java.util.HashSet;
import org.junit.Test;

public class SpiralTest {

    /**
     * @Title: 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
     *         示例 1：
     *         输入:
     *         [
     *         [ 1, 2, 3 ],
     *         [ 4, 5, 6 ],
     *         [ 7, 8, 9 ]
     *         ]
     *         输出: [1,2,3,6,9,8,7,4,5]
     *
     *
     *         |
     *         -------->y轴
     *         |
     *         |
     *         |
     *         x轴
     * @date: 2019年11月17日下午9:20:28
     * @author: zhangxue
     */
//	输出: [1,2,3,4,8,12,11,10,9,5,6,7]
//	int[][] matrix = {
//			{ 1, 2, 3, 4 }, 
//			{ 5, 6, 7, 8 }, 
//			{ 9,10,11,12 },
//	};
    int[][] matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, -1, 11, 12},
            {9, 10, 11, 12},
            {9, 10, 11, 12},
            {9, 10, 11, 12},
            {9, 10, 11, 12}
    };

//	输出: [1,2,3,6,9,8,7,4,5]
//	int[][] matrix = {
//			{ 1, 2, 3 }, 
//			{ 4, 5, 6 }, 
//			{ 7, 8, 9 }
//	};

    int m = matrix[0].length;//m列

    int n = matrix.length;//n行

    int[] result = new int[m * n];

    int x = 0;// 作为n的指针

    int y = 0;// 作为m的指针

    boolean xOrY = false;// true 是x进行变化，false是y进行变化

    boolean dis = true;//true 是 +， false 是 -

    HashSet<Object> set = new HashSet<>();

    @Test
    public void test1() {
        int resultIndex = 0;
        while (true) {
            result[resultIndex] = matrix[x][y];
            set.add(x + "." + y);//用于去重

            // 已经填充的最后一个了，就可以退出了
            if (resultIndex == result.length - 1) {
                break;
            }

            // 判断是否需要换方向
            if (xOrY) {//x
                if (!this.forecastX()) {//预测下一步  下一步已经到头
                    xOrY = false;//修改方向
                    // 继续预测下一步
                    if (!this.forecastY()) {//下一步也已经到头
                        dis = !dis;//+/-取反
                    }
                }
            } else {//y
                if (!this.forecastY()) {//预测下一步 下一步已经到头
                    xOrY = true;//修改方向
                    // 继续预测下一步
                    if (!this.forecastX()) {//下一步也已经到头
                        dis = !dis;//+/-取反
                    }
                }
            }
            if (xOrY) {//x
                x = dis ? ++x : --x;
            } else {
                y = dis ? ++y : --y;
            }
            resultIndex++;
        }
        System.out.println(Arrays.toString(result));
    }

    /**
     * @return true 正常放下走
     * @Title: 预测x轴
     * @Description:
     * @date: 2019年11月17日下午10:38:45
     * @author: zhangxue
     */
    public boolean forecastX() {
        int forecast = (dis ? x + 1 : x - 1);
        if (forecast == -1 || forecast == n) {//当前已经达到极限，不能往下走了
            return false;
        }
        return !set.contains(forecast + "." + y);// 预测的坐标已经会用使用过了
    }

    public boolean forecastY() {
        int forecast = (dis ? y + 1 : y - 1);
        if (forecast == -1 || forecast == m) {//当前已经达到极限，不能往下走了
            return false;
        }
        return !set.contains(x + "." + forecast);// 预测的坐标已经会用使用过了
    }

}
